package tree;

import java.util.ArrayList;
import java.util.List;

/**
 * @author : Rookie
 * @description : 二叉树根节点到指定节点的路径
 * @date : 2023/10/14
 */
public class RootToTargetNodePath {

    public static void main(String[] args) {
        int[] input = {3, 9, 20, -1, -1, 15, 7};
        int target = 15;

        TreeNode root = BinaryTreeUtil.buildTree(input);
        if (root == null) {
            return;
        }
        List<Integer> path = new ArrayList<>();
        List<String> result = new ArrayList<>();
        traversal(root,target,path,result);
        System.out.println(result);
    }

    private static void traversal(TreeNode node, int target, List<Integer> path,List<String> result) {
        // 根
        path.add(node.element);
        if (node.element == target) {
            result.add(addArrow(path));
            return;
        }

        // 左
        if (node.left != null) {
            traversal(node.left,target,path,result);
            path.remove(path.size() - 1);
        }

        // 右
        if (node.right != null) {
            traversal(node.right, target, path, result);
            path.remove(path.size() - 1);
        }
    }

    private static String addArrow(List<Integer> path) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < path.size() - 1; i++) {
            sb.append(path.get(i)).append("->");
        }
        return sb.append(path.get(path.size() -1)).toString();
    }
}
